package com.company.Sort;

import java.io.*;
import java.util.PriorityQueue;

/**
 * Created by v on 16-12-11.
 */
public class ExternalSort {
    private static final int SIZE=100000;

    private static DataInputStream input;
    private static DataOutputStream output;

    private static int size=0;

    private static long[] begin;
    private static long[] end;
    private static int partNumber;
    private static long current;

    //不允许创建该对象
    private ExternalSort(){};

    public static void sort(File file) throws IOException{
        if(!file.exists()){
            throw new FileNotFoundException();
        }

        input=new DataInputStream(
                new BufferedInputStream(new FileInputStream(file)));

        File temp=new File(file.getPath()+".temp");

        temp.createNewFile();

        output=new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(temp)));

        begin=new long[(int)(file.length()/SIZE/4)+2];
        end=new long[(int)(file.length()/SIZE/4)+2];

        sortPart();
        input.close();
        output.close();
        merge(temp);
        temp.renameTo(file);
    }

    //用替换选择产生有序分段
    private static void sortPart(){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        PriorityQueue<Integer> queue1=new PriorityQueue<>();

        partNumber=0;
        begin[0]=0;

        //用于判断是否已经读完了数据
        boolean  z=true;

        //用于标记文件位置
        current=0;

        //读取其中的数据,制造第一个有序分段
        for(int i=0;i<SIZE;i++){
            try {
                queue.offer(input.readInt());
            }catch (IOException e){
                z=false;
                break;
            }
        }

        signPart();

        while (z){
            z=writeSortPart(queue,queue1);

            if(z){
                z=writeSortPart(queue1,queue);
            }
        }
    }

    //进行有序分段的写入,并且把大于优先队列的部分写入死区
    private static boolean writeSortPart(
            PriorityQueue<Integer> queue,
            PriorityQueue<Integer>queue1){
        boolean z=true;

        while (!queue.isEmpty()){
            try {
                //比较读入数字，若对于或等于将要输出值，则放入优先队列当中
                int in=input.readInt();
                if(in>=queue.peek()){
                    queue.offer(in);
                }else {
                    queue1.offer(in);
                }

                output.writeInt(queue.poll());
                current++;
            }catch (IOException ex){
                z=false;
                break;
            }
        }

        //若已经读完，则按规则输出
        if (!z){
            while (true){
                try {
                    output.writeInt(queue.poll());
                    current++;
                }catch (Exception ex){
                    break;
                }
            }

            signPart();

            while (true){
                try {
                    output.writeInt(queue1.poll());
                    current++;
                }catch (Exception ex){
                    break;
                }
            }
        }

        //把文件的分段信息储存起来
        signPart();

        return z;
    }

    //循环的方法归并两个有序片段到目标文件
    private static void merge (File file) throws IOException{
        while (partNumber>1){
            File temp1=new File(file.getPath()+"1");
            File temp2=new File(file.getPath()+"2");

            temp1.createNewFile();
            temp2.createNewFile();

            DataInputStream input=new DataInputStream(
                    new BufferedInputStream(new FileInputStream(file)));

            DataInputStream input1=new DataInputStream(
                    new BufferedInputStream(new FileInputStream(temp1)));
            DataOutputStream output1=new DataOutputStream(
                    new BufferedOutputStream(new FileOutputStream(temp1)));
            DataOutputStream output2=new DataOutputStream(
                    new BufferedOutputStream(new FileOutputStream(temp2)));

            current=end[(partNumber-1)/2];

            //记录分别有多少段
            int part1=(partNumber-1)/2+1;
            int part2=partNumber;
            partNumber=0;
            size=0;

            //copy一半到tmp1处
            for(int i=0;i<current;i++) {
                output1.writeInt(input.readInt());
            }
            output1.close();

            //循环合并各个分段
            for(int i=0,j=part1;i<part1&&j<part2;i++,j++){
                long allSize=end[i]-begin[i]+end[j]-begin[j];
                merge(input1,input,output2,
                        end[i]-begin[i],end[j]-begin[j]);
            }

            //如果为段落数为奇数，必然会剩下一个分段在file处
            if(part2%2==1){
                long size=end[part1-1]-begin[part1-1];
                for(int i=0;i<size;i++){
                    int n=input1.readInt();
                    output2.writeInt(n);
                }

                begin[partNumber]=end[partNumber-1];
                end[partNumber]=begin[partNumber]+size;
                partNumber++;
            }

            output2.close();
            input.close();
            input1.close();
            temp2.renameTo(file);
            temp1.delete();
        }
    }

    //归并两个分段
    private static void merge(DataInputStream input1,DataInputStream input2,
                          DataOutputStream output,
                          long size1,long size2)throws IOException{
        int in1=input1.readInt();
        int in2=input2.readInt();

        int i=1;
        int j=1;

        while (true){
            if(in1<in2){
                output.writeInt(in1);
                if(i++<size1) {
                    in1 = input1.readInt();
                }else {break;}
            }else {
                output.writeInt(in2);
                if(j++<size2) {
                    in2 = input2.readInt();
                }else {break;}
            }
        }

        //查看跳出点，把另外的一个点存入到ouput
        if(i<=size1){
            output.writeInt(in1);
        }

        if(j<=size2){
            output.writeInt(in2);
        }

        while (i++<size1){
            in1 = input1.readInt();
            output.writeInt(in1);
        }

        while (j++<size2){
            in2=input2.readInt();
            output.writeInt(in2);
        }

        //标记新的段落
        if(partNumber!=0){
            begin[partNumber]=end[partNumber-1];
        }
        end[partNumber]=begin[partNumber]+size1+size2;
        partNumber++;
    }

    //标记分段
    private static void signPart(){
        //不允许储存大小为０的分段
        if(current==begin[partNumber]){
            return;
        }

        if(partNumber!=0){
            begin[partNumber]=end[partNumber-1];
        }
        end[partNumber]=current;
        partNumber++;
    }
}